/*
Generatore di grafi casuali

*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "glpk.h"


typedef struct { double w; } e_data;	// struttura per il peso degli archi

int randomf(int, int);	// restituisce un intero casuale compreso nel range descritto dai parametri (inclusi)
void itoa(int, char[]);	// converte l'int in stringa, salvandola nel puntatore delscritto al secondo parametro
void reverse(char[]);	// inverte la stringa sovrascrivendola

int exists_arc(glp_graph*, int, int);	// restituisce  1 se (i,j) è in G, 0 altrimenti

e_data* get_e_data(glp_arc*);	// restituisce un puntatore alla struttura e_data relativa all'arco in input
double get_arc_w(glp_arc*);	// restituisce il peso dell'arco in input
void set_arc_w(glp_arc*,double);// pone il peso dell'arco in input pari al double fornito

int custom_write_graph(glp_graph *, char*); // scrive su file il grafo fornito in input. Se il file non esiste lo crea, altrimenti sovrascrive
int custom_read_graph(glp_graph *, char*); // crea un grafo (primo parametro) a partire da file (secondo parametro)

int main(void) {
	const int min_n = 5; 	// Minimo numero di nodi (incluso)
	const int max_n = 15;	// Massimo numero di nodi (incluso)
	const int min_w = 0;
	const int max_w = 255;

	glp_graph *G, *Greaded;
	glp_arc* arcp;
	e_data* e_datap;
	int i, v1, v2, n, e;
	double w;
	char str[128];
	char* filename = "randgraph";
	
	// Inizializzazione variabili
	strcpy(str, "");
	
	// Generazione della dimensione del grafo
	srand(time(NULL));
	n = randomf(min_n,max_n); 
	e = randomf(n-1,n*(n-1));	// il grafo deve essere connesso quindi il min è n-1 nodi
					// cappi ed archi ripetuti sono proibiti, mentre archi tipo (x,y) e (y,x) sono permessi
					// ogni nodo ha quindi al più n-1 archi uscenti, dunque al più n*n-1 archi

	// Creazione grafo
	G = glp_create_graph(0, sizeof(e_data)); // pesato sugli archi
	glp_set_graph_name(G, "Grafo casuale");
	
	// Inserimento nodi
	for (i = glp_add_vertices(G, n) ; i <= n ; i++){
		strcpy(str,"");		
		itoa(i,str);
		glp_set_vertex_name(G, i, str);

	}

	// Inserimento archi per garantire la connessione
	for (i = 1 ; i <= n-1 ; i++){
		//sto connettendo il nodo i
		if(rand()%2 == 1){	//rendo casuale la direzione dell'arco che connette i
			// genero un arco (i,random)
			v1 = i;
			v2 = randomf(1,n);
			
			while(v1 == v2 || exists_arc(G,v1,v2) ){ // proibisce cappio o ripetizione di arco
				// calcolo un nuovo arco che garantisce la copertura del nodo corrente (con la stessa direzione)
				v2 = randomf(1,n);
			}
		}else{
			// genero un arco (random,i)
			v1 = randomf(1,n);
			v2 = i;
			while(v1 == v2 || exists_arc(G,v1,v2) ){  // proibisce cappio o ripetizione di arco
				// calcolo un nuovo arco che garantisce la copertura del nodo corrente (con la stessa direzione)
				v1 = randomf(1,n);
			}
			
		}
		
		
		arcp = glp_add_arc(G,v1,v2);
		w = (double)randomf(min_w,max_w);
		set_arc_w(arcp,w);

	}
	

	// Inserimento archi
	for (i = n; i <= e ; i++){
		v1 = randomf(1,n);
		v2 = randomf(1,n);
		
		
		while(v1 == v2 || exists_arc(G,v1,v2) ){  // proibisce cappio o ripetizione di arco		
			// calcola un nuovo arco casuale

			// Attenzione, se restano pochi archi inseribili in un grafo molto grande può richiedere tempo
			// 	Richede qualche secondo per generare grafi completi di circa 200 nodi

			v1 = randomf(1,n);
			v2 = randomf(1,n);
		}
		
		arcp = glp_add_arc(G,v1,v2);
		w = (double)randomf(min_w,max_w);
		set_arc_w(arcp,w);

	}
	
	
	printf("Il grafo generato contiene %d nodi e %d archi.\n",n,e);
	custom_write_graph(G,"filename.our");
	
	printf("Procedo con la lettura da file.\n");
	Greaded = glp_create_graph(0, sizeof(e_data)); // pesato sugli archi
	custom_read_graph(Greaded,"filename.our");
	
	custom_write_graph(Greaded,"filename2.our");
	
	return 0;
	
}

void itoa(int n, char s[])
 {
     int i, sign;
 
     if ((sign = n) < 0)  /* record sign */
         n = -n;          /* make n positive */
     i = 0;
     do {       /* generate digits in reverse order */
         s[i++] = n % 10 + '0';   /* get next digit */
     } while ((n /= 10) > 0);     /* delete it */
     if (sign < 0)
         s[i++] = '-';
     s[i] = '\0';
     reverse(s);
 }

void reverse(char s[])
 {
     int i, j;
     char c;
 
     for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
     }
 }

int randomf(int min,int max){
	return min + (rand()%(max+1-min));
}

int exists_arc(glp_graph *G, int i, int j){   // G grafo da controllare, i coda, j testa
	glp_arc* arcp = G->v[i]->out;
	while(arcp != NULL){
		//printf("found %d-%d\n",i,arcp->head->i);
		if(arcp->head->i == j){
			return 1;
		}
		
		arcp = arcp->t_next;
	}
	return 0;
}

e_data* get_e_data(glp_arc* e){
	return (e_data*)e->data;
} 

void set_arc_w(glp_arc* e, double d){
	get_e_data(e)->w = d;
	return;
}

double get_arc_w(glp_arc* e){
	return get_e_data(e)->w;
}

int custom_write_graph(glp_graph *G, char* filename){
	FILE* fp;
	int i,tail,head;
	double w;
	glp_arc* arcp;
	
	fp = fopen(filename, "w");
	
	fprintf(fp,"%d %d\n",G->nv,G->na);  // Scrive il numero di archi e di nodi
	
	for(i = 1; i <= G->nv; i++){
		//Per ogni nodo nel grafo
		arcp = G->v[i]->out; //lista di archi uscenti dal nodo corrente
		while(arcp != NULL){
			tail = arcp->tail->i;
			head = arcp->head->i;
			w = get_arc_w(arcp);
			
			fprintf(fp,"%d %d %lf\n",tail,head,w);

			arcp = arcp->t_next;
		}
	} 
	
	
	fclose(fp);
	return 0;
}



int custom_read_graph(glp_graph *G, char* filename){
	FILE* fp;
	int n,e,i,v1,v2;
	double w;
	glp_arc* arcp;
	char str[128];

	fp = fopen(filename, "r");
	
	// TODO erase del grafo in input (per sicurezza)
		
	// Istanziazione grafo
	glp_set_graph_name(G, "Grafo letto");
		
	fscanf(fp,"%d %d\n",&n,&e); // la prima riga contiene numero di nodi e archi, separati da uno spazio
	
	// Inserimento nodi
	for (i = glp_add_vertices(G, n) ; i <= n ; i++){
		strcpy(str,"");		
		itoa(i,str);
		glp_set_vertex_name(G, i, str);

	}

	// Inserimento archi
	for (i = 1; i <= e ; i++){		
		fscanf(fp,"%d %d %lf\n",&v1,&v2,&w); // le righe successive contengono gli archi nella notazione "coda testa peso"
		
		arcp = glp_add_arc(G,v1,v2);
		set_arc_w(arcp,w);
	}
	
	fclose(fp);
	return 0;
}

